package practice

func combinationSum3(k int, n int) [][]int {
	var res [][]int
	var list []int

	var helper func(index int)
	helper = func(index int) {
		total := sum(list)
		if total == n && len(list) == k {
			tmp := make([]int, k)
			copy(tmp, list)
			res = append(res, tmp)
			return
		} else if total > n || len(list) > k {
			return
		}

		for i := index; i <= 9; i++ {
			list = append(list, i)
			helper(i + 1)
			list = list[:len(list)-1]
		}
	}
	helper(1)
	return res
}

func sum(vals []int) (o int) {
	for _, val := range vals {
		o += val
	}
	return o
}
